package leetcode_201_300;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class LeeCode_239_2 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1}, 1)));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, -1}, 1)));
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,1,2,0,5}, 3)));
    }
    private static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && queue.getLast()[0] <= nums[i]){
                queue.pollLast();
            }
            queue.add(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        int i = 0;
        int l = 0, r = k - 1;
        while (r < n){
            ans[i] = queue.getFirst()[0];
            l++;
            r++;
            i++;
            while (!queue.isEmpty() && queue.getFirst()[1] < l){
                queue.pollFirst();
            }
            if (r < n){
                while (!queue.isEmpty() && queue.getLast()[0] <= nums[r]){
                    queue.pollLast();
                }
                queue.add(new int[]{nums[r], r});
            }
        }
        return ans;
    }
}